Multiple-patterning techniques, such as the sidewall image transfer techniques with two masks per metal layer, have been used to manufacture deep-submicron electronic designs. In typical multiple-patterning approaches, each metal layer is fabricated with multiple photolithographic masks. Using multiple core masks often give rise to systematic or non-systematic alignment or overlay issues between the multiple core masks. The recent development of the self-aligned double patterning (SADP) avoids such alignment or overlay issues by using a core mask and a trim mask (or block mask) for each layer to be printed on a lithographic system. Nonetheless, with the advent of 32 nanometer (32 nm) technology and beyond (e.g., 22 nm, 14 nm, 10 nm, etc.), the trim mask require its own design rules that are often merged with metal layout design rules. Moreover, the trim mask rules are often global in nature and thus pose significant difficulties in physical design implementation tools. For example, a typical line staggering rule may cover as many adjacent lines as possible, and thus modifying one line to obey this line staggering rule may affect the next line(s) or even lines that are distant from the line that is being modified. In addition, the trim mask rules are often directional in nature and depend upon how a mask feature is disposed on the trim mask relative to another mask feature.
In addition, traditional design rule checking is based on geometries or geometric shapes in a physical design of an electronic circuit. Nonetheless, as described earlier, the trim mask rules and requirements are often merged with the layout design rules yet are oftentimes global and directional in nature. Although nothing prevents the application of a traditional design rule checking to an electronic circuit design with 32 nm or beyond technology nodes, the search time and hence the amount of time required for traditional DRC is proportional to log (n) even if the search is done locally (e.g., within a confined region of a layout), where n denotes the number of shapes in the entire layout. Such a traditional DRC approach often requires several hours or even days to complete its execution, especially for a modern electronic circuit design having hundreds of millions or even billions of transistors.
Gridded physical implementation of electronic design has been widely used. Nonetheless, the traditional gridded physical implementation is not correct-by-construction and fails to accommodate the trim mask rules. In addition, conventional physical design approaches are usually dependent upon the total number of shapes in a physical design. In other words, the larger the electronic design is, the longer it takes these conventional physical design tools to perform their respective functions. Regarding multiple-patterning to achieve half-pitch sizes in modern electronics (e.g., designs with 14 nm or 10 nm technology nodes), some previous solutions utilize multiple core masks; and some other previous solutions utilize self-aligned double patterning techniques. Both approaches have their own respective disadvantages and do not accommodate the trim mask rules. For design rule checking, conventional DRC examines the shapes or geometries of a physical design, and the search time for each search of the conventional DRC is proportional to log(n), where n denotes the total number of shapes in the entire design. Another advantage of various embodiments is that the layout may be further simplified to, for example, an edge map or a grid map, that includes only the location data for the shape ends of shapes (e.g., interconnects, pins, pads, terminals, etc.), instead of the full geometry layout data. Such a simplified layout may greatly expedite the efficiency of post-physical design processing tools (e.g., a DRC tool).
Therefore, there is a need for implementing the multiple-patterning aware correct-by-construction routing solutions for an electronic design. More specifically, several embodiments of the invention accommodate such trim mask rules and enable the routing process to find legal paths with no design rule checking while transforming the global problem resulting from the global nature of the trim mask rules into a local problem for the routing process to identify legal paths for semiconductor technologies beyond the 32 nm technology. There is also a need for a new design rule check process and a new violation fixing process for electronic designs having advanced technology nodes such as the 10-nm nodes in modern electronics.